package cn.structure.binarytree;

/**
 * 二叉堆数据结构
 *
 * @author dunlingiz
 * @date 2024/2/27
 */
public class BinaryHeap {

    transient int[] heapArray;

    private int size;

    public BinaryHeap(int capacity) {
        // todo 一些必要性校验
        heapArray = new int[capacity];
        size = 0;
    }

    public BinaryHeap(int[] array) {
        // todo 一些必要性校验，判断是否符合完全二叉树等等
        if (!isCompleteBinaryTree(array)) {
            throw new IllegalStateException("array is not CompleteBinaryTree!");
        }

        heapArray = array;
        size = array.length;
        // TODO 将完全二叉树转换成二叉堆
    }

    /**
     * 判断传入数组是否满足完全二叉数的
     *
     * @param array 数组
     */
    public boolean isCompleteBinaryTree(int[] array) {
        // todo array判断数组是否满足完全二叉树的结构
        return true;
    }

    /**
     * 判断构建的二叉堆是否符合二叉堆的要求
     */
    public boolean isBinaryHeap() {
        return true;
    }

    /**
     * 插入节点
     *
     * @param value
     */
    public void insert(int value) {
        // TODO 1、添加元素    2、上浮操作
    }

    public void remove() {
        // TODO 1、删除堆顶元素   2、将堆末尾元素替换成堆顶元素   3、下沉操作
    }

    /**
     * 上浮操作
     *
     * @param array 待调整的完全二叉树
     */
    public void up(int[] array) {
        int childIndex = array.length - 1;
        int parentIndex = (childIndex - 1) / 2;
        int temp = array[childIndex];
        while (childIndex > 0 && temp < array[parentIndex]) {
            array[childIndex] = array[parentIndex];
            childIndex = parentIndex;
            parentIndex = (childIndex - 1) / 2;
        }
        array[childIndex] = temp;
    }

    /**
     * 下沉操作
     */
    public void down() {

    }
}
